/*
 * @lc app=leetcode.cn id=332 lang=cpp
 *
 * [332] 重新安排行程
 */

// @lc code=start
class Solution
{
private:
    unordered_map<string, map<string, int>> m; //出发机场,(到达机场,出现次数)
    vector<string> res;
    bool backtracking(vector<vector<string>> &tickets, int num)
    {
        //终止条件
        //因为题目说了每张机票都需要使用
        if (num == m.size() + 1)
        {
            return true;
        }
        //这里其实不需要for循环每层 因为只需要找到一条路
        //更正 因为可能这条路不行 还是需要循环
        for (pair<const string, int> &a : m[res.back()])
        {
            if (a.second > 0)
            {
                a.second--;
                res.push_back(a.first);
                backtracking(tickets, num + 1);
                res.pop_back();
                a.second++;
            }
        }
    }

public:
    vector<string> findItinerary(vector<vector<string>> &tickets)
    {
        //重新安排行程 按字母序小的开始 注意避免死循环
        //初始化
        for (const vector<string> &str : tickets)
        {
            m[str[0]][str[1]]++;
        }
        res.push_back("JKL");
        backtracking(tickets, 1);
        return res;
    }
};
// @lc code=end

